Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the network elements. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, how protocol data units should be handled or routed through the network by the network elements, and how information such as routing information should be exchanged between the network elements.
Ethernet is a well known networking protocol that has been defined by the Institute of Electrical and Electronics Engineers (IEEE) as standard 802.1 In Ethernet network architectures, devices connected to the network compete for the ability to use shared telecommunications paths at any given time. Where multiple bridges or nodes are used to interconnect network segments, multiple potential paths to the same destination often exist. The benefit of this architecture is that it provides path redundancy between bridges and permits capacity to be added to the network in the form of additional links. However to prevent loops from being formed, a spanning tree was generally used to restrict the manner in which traffic was broadcast or flooded on the network. A characteristic of a spanning tree is that there is only one path between any pair of destinations in the network, and therefore it was possible to “learn” the connectivity associated with a given spanning tree by watching where packets came from. However the spanning tree itself was restrictive and often led to over-utilization of the links that were on the spanning tree and non-utilization of the links that weren't part of the spanning tree.
To overcome some of the limitations inherent in Ethernet networks implementing a spanning tree, a link state protocol controlled Ethernet network was disclosed in application Ser. No. 11/537,775, filed Oct. 2, 2006, entitled “Provider Link State Bridging,” the content of which is hereby incorporated herein by reference. As described in greater detail in that application, rather than utilizing a learned network view at each node by using the Spanning Tree Protocol (STP) algorithm combined with transparent bridging, in a link state protocol controlled Ethernet network the bridges forming the mesh network exchange link state advertisements to enable each node to have a synchronized view of the network topology. This is achieved via the well understood mechanism of a link state routing system. The bridges in the network have a synchronized view of the network topology, have knowledge of the requisite unicast and multicast connectivity, can compute a shortest path connectivity between any pair of bridges in the network, and can individually populate their forwarding information bases (FIBs) according to the computed view of the network.
When all nodes have computed their role in the synchronized view and populated their FIBs, the network will have a loop-free unicast tree to any given bridge from the set of peer bridges (those that require communication to that bridge for whatever reason); and a both congruent and loop-free point-to-multipoint (p2mp) multicast tree from any given bridge to the same set or subset of peer bridges per service instance hosted at the bridge. The result is the path between a given bridge pair is not constrained to transmitting the root bridge of a spanning tree and the overall result can better utilize the breadth of connectivity of a mesh. In essence every bridge roots one or more trees which define unicast connectivity to that bridge, and multicast connectivity from that bridge.
When customer traffic enters a provider network, the customer MAC address (C-MAC DA) is resolved to a provider MAC address (B-MAC DA), so that the provider may forward traffic on the provider network using the provider MAC address space. Additionally, the network elements on the provider network are configured to forward traffic based on Virtual LAN ID (VID) so that different frames addressed to the same destination address but having different VIDs may be forwarded over different paths through the network. In operation, a link state protocol controlled Ethernet network may associate one VID range with shortest path forwarding, such that unicast and multicast traffic may be forwarded using a VID from that range, and traffic engineering paths may be created across the network on paths other than the shortest path, and forwarded using a second VID range.
FIG. 1 is a functional block diagram of an example of a portion of a link state protocol controlled Ethernet network 10. As shown in FIG. 1, the network 10 in this example includes a plurality of network elements 12, interconnected by links 14. The network elements 12 exchange hello messages to learn adjacencies of other network elements, and exchange link state advertisements to enable each node to build a link state database that may be used to calculate shortest paths between ingress and egress nodes through the network.
Examples of link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS), although other link state routing protocols may be used as well. IS-IS is described, for example, in ISO 10589, and IETF RFC 1195, the content of each of which is hereby incorporated herein by reference.
In addition to installing shortest path unicast forwarding state, the nodes may also install forwarding state for multicast trees on the network. An example of a way to implement multicast in a link state protocol controlled Ethernet network is described in greater detail in U.S. patent application Ser. No. 11/702,263, filed Feb. 5, 2007, entitled “Multicast Implementation in a Link State Protocol Controlled Ethernet Network” the content of which is hereby incorporated herein by reference. As described in that application, link state advertisements may be used to advertise multicast group membership to cause forwarding state for a multicast group to be installed on the network. In particular, each source in a given multicast group may be assigned a destination MAC Address (DA) that is used to forward the frames on the network. The nodes on the network install forwarding state for the source/group tree if they determine that they are on a shortest path from the multicast source to one of the destination nodes advertising via the link state protocol an “interest” in the multicast group.
Interest in a multicast may be based on the community of interest identifier such as the I-SID, such that a node on the network will install forwarding state for a multicast group when it is on a shortest path between a source and destination that have both advertised interest in the community of interest identifier associated with the multicast group. An I-SID normally is associated with 802.1ah and implies an additional MAC header (customer source & destination MAC addresses). However, the I-SID has utility even if a C-MAC header is not used, because an I-SID value can identify the participants in a specific instance of mutual connectivity The forwarding state, however, is based on the multicast DA and VID associated with the multicast.
In operation, multiple nodes on the network may advertise interest in a particular I-SID. The nodes on the network keep track of which nodes have advertised interest in which I-SID and will install forwarding state for a DA/VID pair associated with the I-SID if they are on the shortest path between two nodes that have advertised interest in the particular I-SID. This allows forwarding state to be installed for communities of interest without requiring flooding of the frames on the network.
Link state protocol controlled Ethernet networks operate at the link layer (Layer 2). That is, the ingress node creates a MAC header that may be used to switch the frame across the Ethernet network, e.g. from Node A to Node E. Other networks, such as Internet Protocol (IP) networks, operate at a higher layer such as Layer 3 (network layer). IP networks forward packets based on an IP address of an IP header associated with an IP packet.
FIGS. 2 and 3 show two common ways in which IP routing may be used to forward an IP packet on a conventional IP network. In the example shown in FIG. 2, network 20 interconnects network X and network Y. The network 20 includes many routers 22 and may have a configuration similar to the network shown in FIG. 1. In FIGS. 2 and 3 it has been assumed that the path through network 20 will be via nodes A, B, C, D, E. To simplify explanation of the operation of the network 20, routers that are not on the selected path between networks X and Y have not been shown in FIGS. 2 and 3.
Generally when a packet arrives at router 22A, the router will perform an IP lookup based on the IP address in the packet and determine a next hop for the packet on the IP network. The router will then resolve the next hop IP address to a layer 2 MAC address and create a Layer 2 MAC header for the packet and transmit the packet on a link 24A to the next hop router along the path to the destination. In this example, router 22A will add a MAC header with a Destination MAC Address (DA)=I, and a Source MAC Address (SA)=H. The router 22A will then forward the packet onto the link to router 22B.
When router 22B receives the packet it will strip off the MAC header and perform a lookup on the IP header. It will then encapsulate the packet with a new MAC header which in this example has DA=K, and SA=J. It will then forward the packet toward its destination on link 24B. This strip and add process will be performed at each router along the path until the packet arrives at the destination network Y. Thus, for conventional IP forwarding, each router along the path will strip off the outer 802.3 header, perform an IP lookup to route the packet, and then add a new 802.3 header to forward the packet across the network. This process is repeated hop by hop with each router stripping off the MAC header and performing an IP lookup to route the packet through the network.
FIG. 3 shows another manner in which IP routing may be implemented. In the example shown in FIG. 3, MPLS is used to reduce the number of IP lookups performed at the various routers in the network. In an MPLS network, a plurality of Label Switched Paths (LSPs) will be established through the MPLS network. The particular manner in which LSPs are determined and created through the network is well known. In the example shown in FIG. 3 it will be assumed that the label switched path includes nodes A, B, C, D, E. When a packet arrives at the edge router 32A, the edge router 32A will perform an IP lookup to determine which label should be used to switch the IP packet onto the LSP through the MPLS network to reach network Y. The edge router 32A will then apply that label to the packet. The edge router 32A will also determine a next hop for the packet on the path and apply a MAC header to the packet to cause the packet to be forwarded to the next hop on the path (router 32B).
Router 22B will strip the outer MAC header and read the MPLS label. When the LSP was established through the network the label distribution protocol will have established an association between label 100 and label 210 for a particular IP Forwarding Equivalence Class such that when the router 32B receives a packet with MPLS label 100 it will replace the label with a new MPLS label 210 before adding a new MAC header and forwarding to the outbound interface. Similar to the operation in FIG. 2 before forwarding the packet, router 32B will add a new MAC header to the packet which, in this instance, is SA=J, DA=K to identify the source MAC address as MAC J on router 32B and the destination MAC address as MAC K on router 32C.
MPLS thus allows a single IP route lookup to be performed at the edge of the MPLS network, and allows label switching to be used instead of IP lookups to forward the packet across the MPLS network. Edge routers that perform the initial IP lookup and assign the label to the packet to place the packet on the LSP are referred to as Label Edge Routers. Intermediate routers on the MPLS network that perform label switching are commonly referred to as Label Switch Routers (LSRs). Forwarding in an MPLS network is performed by swapping a label after stripping the MAC header at each hop. MPLS forwarding still requires MAC header stripping to occur at every hop across the network (when Ethernet links are employed), requires each LSR to perform a label lookup and label swap, and requires each LSR to then add another MAC header to deliver the packet to the next LSR along the LSP. This process requires more processing and intelligence on each of the nodes which thus results in an expensive solution. Additionally, for this to work the path must be initially set up which in and of itself is a computationally expensive process.
IP networks and network layer protocols in general are supported by lower layer network, such as an Ethernet network. Hence, when a router transmits a network layer packet it will apply a lower layer protocol header such as an Ethernet MAC header to the packet before transmitting the packet on the network. The MAC header is used at the link layer to forward the packet over the Layer 2 network that is providing support for the network layer. Accordingly, it would be advantageous to enable link state protocol controlled Ethernet networks to integrate support for network layers as well.